package leetcode.editor.cn;
//Java：删除链表的倒数第 N 个结点
public class RemoveNthNodeFromEndOfList{
    public static void main(String[] args) {
        Solution solution = new RemoveNthNodeFromEndOfList().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 *
 */
    /**
     * 思路：首先定义一个初始化指针，然后再定义两个开始和结束指针，分别指向初始化指针（防止抛空指针异常）。
     * 然后让开始和结束指针间隔n个节点，然后两个指针同时后移，当最后一个指针到链表尾部了，慢的指针的下一个节点就是要删除的节点
     * 问题一：其他的题目while循环都是end！=null；为什么这个是end.next！=null。
     * 因为这个题目是要找倒数第n个节点，计数是从末尾最后一个节点开始，所以，end不需要遍历到为null，到末尾即可
     * <p>
     * 问题二：为什么初始节点  ListNode start = pre;   ListNode end = pre;start和end都指向虚拟节点？
     * 因为当head有一个节点的时候，如果start指向head，它的next为null，更不会存在 start.next.next；
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode pre = new ListNode(-1, head);
            ListNode start = pre;
            ListNode end = pre;
            while (n != 0) {
                end = end.next;
                n--;
            }

            while (end.next != null) {
                start = start.next;
                end = end.next;
            }
            start.next = start.next.next;
            return pre.next;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}